TDA Week, Kyoto University, 2025
a metric space (X,dX)(X,d_X)
a scale β>0\beta>0
ℛβ(X)\mathcal{R}_\beta(X) is an abstract simplicial complex
V = []; { const height = "500px"; const container = d3.create("div").style("position", "relative"); let svg = container .append("svg") .attr("class", "canvas") .style("margin-left", "15px") .style("width", "90%") .style("height", height) .style("border", "0.5px solid #eee"); const triangles = svg.append("g").attr("class", "triangles"); const edges = svg.append("g").attr("class", "edges"); const vertices = svg.append("g").attr("class", "vertices"); // scale container .append("div") .style("width", "15px") .style("height", height) .style("background", "#eee") .style("position", "absolute") .style("top", "0") .style("bottom", "0") .append("div") .style("width", "100%") .style("height", scale + "px") .style("background", "steelblue"); container .append("div") .style("margin-left", "12px") .style("width", height) .style("display", "inline-block") .style("text-align", "center") .style("transform", "rotate(-90deg)") .style("transform-origin", "top left") .html(tex`\beta`.outerHTML); drawRips(svg, sc.rips(V, scale, 2)); svg.on("click", (e) => { const coord = d3.pointer(e); V.push(coord); drawRips(svg, sc.rips(V, scale, 2)); }); return container.node(); }
import { slider } from "@jashkenas/inputs" sc = require("https://cdn.jsdelivr.net/npm/@tdajs/simplicial-complex@1.2.1/dist/min.js")
drawRips = function (svg, rips) { if (rips.simplices[2]) { svg.selectAll(".triangle") .data(rips.simplices[2]) .join("path") .attr("class", "triangle") .attr("d", (d) => d3.line()(d.map((v) => V[v]))) .attr("fill", "lightgreen") .attr("stroke", "none") .attr("opacity", "0.3"); } if (rips.simplices[1]) { svg.selectAll(".edge") .data(rips.simplices[1]) .join("path") .attr("class", "edge") .attr("d", (d) => d3.line()(d.map((v) => V[v]))) .attr("stroke", "green").attr("stroke-width", "2"); } svg.selectAll(".vertex") .data(V) .join("circle") .attr("class", "vertex") .attr("class", "vertex") .attr("fill", "white") .attr("cx", (d) => d[0]) .attr("cy", (d) => d[1]) .attr("r", "2px") .on("mouseover", function () { d3.select(this).attr("fill", "green").attr("r", "10px"); }) .on("mouseout", function () { d3.select(this).attr("fill", "white").attr("r", "2px"); }); return svg; }
viewof scale = Inputs.range([0, 300], { step: 1, value: 0, label: tex`\beta` }) viewof btn = Inputs.button("clear", { value: null, reduce: () => { V.length = 0; viewof scale.value = 0;viewof scale.dispatchEvent(new CustomEvent("input")); } })
A sample
A Reconstruction
Source: Kyoto City Official Traval Guide
The City of Berlin
Q: How to draw the map of the city from a noisy point-cloud of GPS locations?
Source: mapconstruction.org
Shape: A Shape is modeled as a metric space (M,dM)(M,d_M)
Sample: A finite metric space (X,dX)(X,d_X) close to MM
Goal: Infer the topology of MM from XX.
Estimate only the Betti numbers—number of connected components, cycles, voids, etc—of MM.
construct a topological space M̃\widetilde{M} from XX to retain the topology of MM, i.e., M≃M̃M\simeq\widetilde{M} in some appropriate sense.
Provide a window of resolutions or scales for the Vietoris–Rips complexes for a topologically-faithful reconstruction
Design provable reconstruction algorithms particularly for bad shapes
Reconstruction under different noise models, e.g. the Gromov–Hausdorff distance
Probabilistic guarantees in the face of random samples
Understand the topology of ℛβ(X)\mathcal{R}_\beta(X)
When is the homology of ℛβ(X)\mathcal{R}_\beta(X) finitely generated?
Alternative to the Nerve Lemma for Vietoris–Rips complexes
Implications in Shape Reconstruction
—Metric structures of Riemann & non-Riemann Spaces, page100
Let XX be a length metric space…given by ε\varepsilon-nets Xε0X_\varepsilon^{0} in XX which Hausdorff converges XX…
…One can turn such a space into a path metric space, namely a graph Xε1⊂XX_\varepsilon^{1}\subset X with Xε0X_\varepsilon^{0} as its vertex set, and where two points xx and yy in Xε1X_\varepsilon^{1} within distance δ≤δε\delta\leq\delta_\varepsilon joined by an edge of length δ\delta.
…fll in the small triangles of edges in the graph Xε1X_\varepsilon^{1} by actual 22-dimensional triangles to obtain Xε2⊂XX_\varepsilon^{2}\subset X, then π1(Xε2)=π1(X)\pi_1(X_\varepsilon^{2})=\pi_1(X) for ε,δε→0\varepsilon,\delta_\varepsilon\to0 with ε/δε→∞\varepsilon/\delta_\varepsilon\to\infty.
Hausmann (1995)
For any closed Riemannian manifold MM and 0<β<ρ(M)0<\beta<\rho(M), the Vietoris–Rips complex ℛβ(M)\mathcal{R}_\beta(M) is homotopy equivalent to MM.
{ const svg = d3.create('svg').attr('viewBox', [-width/2, -600, width, 1200]); svg .append('circle') .attr('cx', '0') .attr('cy', '0') .attr('r', 500) .style('fill', 'none') .style('stroke-width', 10) .style('stroke', 'lightgray'); const arc = d3.arc() .innerRadius(490) .outerRadius(510) .startAngle(-rad * Math.PI * 2) .endAngle(rad * Math.PI * 2); svg.append("path") .attr("class", "arc") .attr("d", arc) .attr("fill", rad <= 0.25 ? "#3be57f" : "#bb473f"); svg.append('circle') .attr('cx', 0) .attr('cy', -500) .attr('r', 20) .style('fill', '#3be57f') return svg.node(); }
viewof rad = Inputs.range([0, 0.5], { step: 0.01, value: 0, label: '' })
Hausmann’s Curious Question
What about the Vietoris–Rips complex of a finite, dense subset S⊂MS\subset M?
Gromov–Hausdorff Distance:
Latschev (2001)
Every closed Riemannian manifold MM has an ϵ0>0\epsilon_0>0 such that for any 0<β≤ϵ00<\beta\leq\epsilon_0 there exists some δ>0\delta>0 so that for any sample SS: dGH(S,M)≤δ⟹ℛβ(S)≃M. d_{GH}(S,M)\leq\delta\implies \mathcal R_\beta(S)\simeq M.
the threshold ϵ0=ϵ0(M)\epsilon_0=\epsilon_0(M) depends solely on the geometry of MM. But the theorem did not say how!
δ=δ(β)\delta=\delta(\beta) is a function (a fraction in practice) of β\beta.
The result is qualitative
Nonetheless, the result provides a promising answer to Hausmann’s question, and more!
Metric Graph Reconstruction [J. Appl. & Comp. Top., Majhi (2023)]
Let (G,dG)(G,d_G) be a compact, path-connected metric graph, (S,dS)(S,d_S) a metric space, and β>0\beta>0 a number such that 3dGH(G,S)<β<34ρ(G).3d_{GH}(G,S)<\beta<\frac{3}{4}\rho(G). Then, ℛβ(S)≃G\mathcal R_\beta(S)\simeq G
The result is quantitative
ϵ0=34ρ(G)\epsilon_0=\frac{3}{4}\rho(G)
δ=13β\delta=\frac{1}{3}\beta
The constants are not optimal!
Riemannian Manifold Reconstruction [SoCG’24, DCG, Majhi (2024)]
Let MM be a closed, connected Riemannian manifold. Let (S,dS)(S,d_S) be a compact metric space and β>0\beta>0 a number such that 1ξdGH(M,S)<β<11+2ξmin{ρ(M),π4κ} \frac{1}{\xi}d_{GH}(M,S)<\beta<\frac{1}{1+2\xi}\min\left\{\rho(M),\frac{\pi}{4\sqrt{\kappa}}\right\} for some 0<ξ≤1/140<\xi\leq1/14. Then, ℛβ(S)≃M\mathcal R_\beta(S)\simeq M.
κ\kappa is an upper bound on the sectional curvatures of MM
For ξ=114\xi=\frac{1}{14}:
ϵ0=78min{ρ(M),π4κ}\epsilon_0=\frac{7}{8}\min\left\{\rho(M),\frac{\pi}{4\sqrt{\kappa}}\right\}
δ=β14\delta=\frac{\beta}{14}
Euclidean Submanifold Reconstruction (Majhi 2024)
Let M⊂ℝNM\subset\mathbb R^N be a closed, connected submanifold. Let S⊂ℝNS\subset\mathbb R^N be a compact subset and β>0\beta>0 a number such that 1ξdH(M,S)<β<3(1+2ξ)(1−14ξ)8(1−2ξ)2τ(M) \frac{1}{\xi}d_{H}(M,S)<\beta<\frac{3(1+2\xi)(1-14\xi)}{8(1-2\xi)^2}\tau(M) for some 0<ξ<1/140<\xi<1/14. Then, ℛβ(S)≃M\mathcal R_\beta(S)\simeq M.
τ(M)\tau(M) is the reach of MM
For ξ=128\xi=\frac{1}{28}:
ϵ0=3151352τ(M)\epsilon_0=\frac{315}{1352}\tau(M)
δ=β28\delta=\frac{\beta}{28}
Length space: A metric space with an instrinsic metric
Geodesically complete: a pair can be joined by a length-minimizing path
CAT(κ)\mathrm{CAT}(\kappa): geodesic triangles are “slimmer” than corresponding “model triangles” in a standard space of constant curvature κ\kappa.
Examples:
Lastchev’s Theorem for CAT(κ)\mathrm{CAT}(\kappa) Spaces (Komendarczyk, Majhi, and Tran 2024)
ε\varepsilon-path Metric:
Fix an ε>0\varepsilon>0, proportional to dH(S,X)d_H(S,X)
For any two sample points a,b∈Sa,b\in S, define dSε(a,b)d_S^\varepsilon(a,b) to be the shortest distance when hopping over the points of SS with a step size of ε\varepsilon.
Euclidean Subsets (Komendarczyk, Majhi, and Tran 2024)
Let XX be a geodesic subspace of ℝN\mathbb R^N. Let ξ∈(0,1)\xi\in\left(0,1\right) and β>0\beta>0 be fixed numbers. 0<ε≤β0<\varepsilon\leq\beta such that δβε(X)≤1+(ξ1+ξ)\delta^\varepsilon_{\beta}(X)\leq1+\left(\frac{\xi}{1+\xi}\right), then for any compact subset S⊂ℝNS\subset\mathbb R^N with dH(X,S)<12ξεd_H(X,S)<\frac{1}{2}\xi\varepsilon, we have ℛβε(S)≃X\mathcal{R}_\beta^\varepsilon(S)\simeq X.
Topological Reconstruction (Komendarczyk, Majhi, and Mitra 2025)
Let G⊂ℝNG \subset \mathbb{R}^N be a compact, connected metric graph. Fix any ξ∈(0,14)\xi\in\left(0,\frac{1}{4}\right). For any positive β<ℓ(G)4\beta<\frac{\ell(G)}{4}, choose a positive ε≤β3\varepsilon\leq\frac{\beta}{3} such that δβε(G)≤1+2ξ1+ξ\delta^{\varepsilon}_{\beta}(G)\leq\frac{1+2\xi}{1+\xi}. If S⊂ℝNS\subset \mathbb R^N is compact and dH(G,S)<12ξεd_H(G,S)<\tfrac{1}{2}\xi\varepsilon, then have a homotopy equivalence ℛβε(S)≃G\mathcal R^\varepsilon_\beta(S)\simeq G.
Geometric Reconstruction (Komendarczyk, Majhi, and Mitra 2025)
Let G⊂ℝ2G \subset \mathbb{R}^2 a graph. Fix any ξ∈(0,1−Θ6)\xi\in\left(0,\frac{1-\Theta}{6}\right). For any positive β<min{Δ(G),ℓ(G)12}\beta<\min\left\{\Delta(G),\frac{\ell(G)}{12}\right\}, choose a positive ε≤(1−Θ)(1−Θ−6ξ)12β\varepsilon\leq\frac{(1-\Theta)(1-\Theta-6\xi)}{12}\beta such that δβε(G)≤1+2ξ1+ξ\delta^{\varepsilon}_{\beta}(G)\leq\frac{1+2\xi}{1+\xi}. If S⊂ℝ2S\subset \mathbb R^2 is compact and dH(G,S)<12ξεd_H(G,S)<\tfrac{1}{2}\xi\varepsilon, then the shadow sh(ℛβε(S))sh(\mathcal R_\beta^\varepsilon(S)) is homotopy equivalent to GG. Moreover, dH(sh(ℛβε(S)),G)<(β+12ξε)d_H(sh(\mathcal R_\beta^\varepsilon(S)),G)<\left(\beta+\frac{1}{2}\xi\varepsilon\right).